// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表

// 例题 5:
// 描述
//        你有一个背包，最多能容纳的体积是V。
//
//        现在有n种物品，每种物品有任意多个，第i种物品的体积为 v[i],价值为 w[i]。
//
//        （1）求这个背包至多能装多大价值的物品？
//        （2）若背包恰好装满，求至多能装多大价值的物品？
//        输入描述：
//        第一行两个整数n和V，表示物品个数和背包体积。
//        接下来n行，每行两个数 v[i] 和 w[i]，表示第i种物品的体积和价值。
//        1 <= n, V <= 1000
//
//        输出描述：
//        输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
//        示例1
//        输入：
//        2 6
//        5 10
//        3 1
//
//        输出：
//        10
//        2
//
//        示例2
//        输入：
//        3 8
//        3 10
//        9 1
//        10 1
//
//        输出：
//        20
//        0
//
//        说明：
//        无法恰好装满背包。
//        示例3
//        输入：
//        6 13
//        13 189
//        17 360
//        19 870
//        14 184
//        6 298
//        16 242
//
//        输出：
//        596
//        189
//
//        说明：可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

import java.util.Scanner;

public class UnboundedKnapsack {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int V = in.nextInt();
            int[] v = new int[n + 1];
            int[] w = new int[n + 1];

            for(int i = 1; i <= n; i++){
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }

            int[][] dp1 = new int[n + 1][V + 1];

            for(int i = 1; i <= n; i++){
                for(int j = 0; j <= V; j++){
                    dp1[i][j] = dp1[i - 1][j];
                    if(j >= v[i]){
                        dp1[i][j] = Math.max(dp1[i][j], dp1[i][j - v[i]] + w[i]);
                    }
                }
            }

            System.out.println(dp1[n][V]);

            int[][] dp2 = new int[n + 1][V + 1];

            for(int j = 1; j <= V; j++){
                dp2[0][j] = -1;
            }

            for(int i = 1; i <= n; i++){
                for(int j = 0; j <= V; j++){
                    dp2[i][j] = dp2[i - 1][j];
                    if(j >= v[i] && dp2[i][j - v[i]] != -1){
                        dp2[i][j] = Math.max(dp2[i][j], dp2[i][j - v[i]] + w[i]);
                    }
                }
            }
            if(dp2[n][V] == -1) System.out.println(0);
            else System.out.println(dp2[n][V]);
        }
    }
}
